package ua.mykola.string;

public class RabinKarpSubstringSearch
{

    private static final int R = 256;// alphabet size

    private static final int PRIME = 997;

    private final String pattern;

    private final int patHash;

    private final int shift;

    public RabinKarpSubstringSearch(String pattern)
    {
        this.pattern = pattern;
        patHash = calcHash(pattern);
        int shift = 1;
        for (int i = 0; i < pattern.length() - 1; i++)
        {
            shift = (shift * R) % PRIME;
        }
        this.shift = shift;
    }

    private int calcHash(String string)
    {
        int hash = 0;
        for (int i = 0; i < pattern.length(); i++)
        {
            hash = (hash * R + string.charAt(i)) % PRIME;
        }
        return hash;
    }

    public int findIn(String text)
    {
        int hash = calcHash(text);
        if (hash == patHash)
            return 0;
        for (int i = 0; i < text.length() - pattern.length(); i++)
        {
            hash = (((hash - text.charAt(i) * shift % PRIME + PRIME) % PRIME) * R + text.charAt(i + pattern.length())) % PRIME;
            if (hash == patHash)
                return i + 1;
        }
        return -1;
    }
}
